package com.wfm.leetcode.editor.cn;

/**
 * 寻找重复数
 * 2025-02-12 17:02:58
 *
 * 数组值：2  1  3  4  3
 * 下标 ： 0  1  2  3  4
 * 类似链表寻找是否有环，以及环入口在哪。环的入口处就是数字重复的地方。
 * 每次移动是根据数组值，移动到对应下标。比如第一个数组值是2，下次移动就移动下标为2的3
 * 为了反正初始时候，就在环入口，因此规定了nums[i]属于[1,n]。即可以保证nums[0]!=0所以可以从i=0开始遍历。
 * 时间：O(n)
 * 空间：O(1)
 */
class FindTheDuplicateNumber {

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new FindTheDuplicateNumber().new Solution();
        int[] nums = {1,3,4,2,2};
        int i = solution.findDuplicate(nums);
        System.out.println(i);
        
    }
}